package 链表;

/**
 * <p>
 * https://leetcode-cn.com/problems/middle-of-the-linked-list/
 * 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
 * 如果有两个中间结点，则返回第二个中间结点。
 * </p>
 *
 * @author AJun
 * @since 2020/8/12
 */
public class _876_链表的中间结点 {

    // 数组法
    public ListNode middleNode0(ListNode head) {
        ListNode[] A = new ListNode[100];
        int t = 0;
        while (head != null) {
            A[t++] = head;
            head = head.next;
        }
        return A[t / 2];
    }

    // 单指针法
    public ListNode middleNode(ListNode head) {
        ListNode curr = head;
        int count = 0;
        while (curr != null) {
            count++;
            curr = curr.next;
        }
        int k = 0;
        curr = head;
        while (k < count / 2) {
            k++;
            curr = curr.next;
        }
        return curr;
    }

    // 快慢指针法: 快指针到达末尾，慢指针刚好在中间
    public ListNode middleNode2(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

}
